package com.lishem.carl._07tree;

import com.lishem.common.TreeNode;

/**
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
 * <p>
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * <p>
 * 示例 1:
 * <p>
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * <p>
 * 输出: [3,9,20,null,null,15,7]
 * <p>
 * 示例 2:
 * <p>
 * 输入: preorder = [-1], inorder = [-1]
 * <p>
 * 输出: [-1]
 */
public class _23LetCode105_从前序与中序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }
        if (inLeft == inRight) {
            return new TreeNode(inorder[inLeft]);
        }
        int rootValue = preorder[preLeft];
        int rootValueIn = -1;
        for (int i = inLeft; i <= inRight; i++) {
            if (rootValue == inorder[i]) {
                rootValueIn = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootValue);
        root.left = buildTree(preorder, inorder, preLeft + 1, preLeft + rootValueIn - inLeft, inLeft, rootValueIn - 1);
        root.right = buildTree(preorder, inorder, preLeft + rootValueIn - inLeft + 1, preLeft, rootValueIn + 1, inRight);
        return root;
    }


    public static void main(String[] args) {
        _23LetCode105_从前序与中序遍历序列构造二叉树 sol = new _23LetCode105_从前序与中序遍历序列构造二叉树();
        TreeNode treeNode = sol.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(1);
    }

}
